"""
难度：中等
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。
返回你可以印出的非空字母序列的数目。
注意：本题中，每个活字字模只能使用一次。
示例 1：
输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
示例 2：
输入："AAABBC"
输出：188
示例 3：
输入："V"
输出：1
"""
class Solution:
    ans = 0
    def numTilePossibilities(self, tiles: str) -> int:
        tile_map =dict()
        for title in tiles:
            if title not in tile_map:
                tile_map[title] = 1
            else:
                tile_map[title] += 1
        self.backtrack(tile_map)

        return self.ans

        # AAB
        # A:1
        # B:1
    def backtrack(self, tile_map):
        for key, value in tile_map.items():
            if value == 0:
                continue
            self.ans += 1
            tile_map[key] -= 1
            self.backtrack(tile_map)
            tile_map[key] += 1

if __name__ == "__main__":
    s= Solution()
    tiles = "AAB"
    print(s.numTilePossibilities(tiles))